package loadbalance;

import java.util.*;

public class ConsistentHashLoadBalance implements LoadBalance{
    private static SortedMap<Integer, String> hashRing;
    private static Map<Integer, List<Integer>> real2Virtual;
    private static final int virtualNum = 100;

    @Override
    public String balance(List<String> addressList, String serviceName) {
        if(hashRing == null){
            hashRing = new TreeMap<>();
            real2Virtual = new HashMap<>();
            for (String address : addressList) {
                addNode(address);
            }
        }
        int hash = getHash(serviceName);
        SortedMap<Integer, String> subMap = hashRing.tailMap(hash);
        if(subMap.isEmpty()){
            return hashRing.get(hashRing.firstKey());
        }
        return subMap.get(subMap.firstKey());
    }

    private void addNode(String address){
        int hash = getHash(address);
        hashRing.put(hash, address);
        List<Integer> list = new ArrayList<>();
        for(int i = 1; i <= virtualNum; i++){
            String virtualNode = address + "-" + i;
            int virtualHash = getHash(virtualNode);
            hashRing.put(virtualHash, address);
            list.add(virtualHash);
        }
        real2Virtual.put(hash, list);
    }
    private void deleteNode(String address){
        int hash = getHash(address);
        hashRing.remove(hash);
        for (int virtualHash : real2Virtual.get(hash)) {
            hashRing.remove(virtualHash);
        }
        real2Virtual.remove(hash);
    }
    private static int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash ^ str.charAt(i)) * p;
            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            if(hash < 0) {
                hash = Math.abs(hash);
            }
        }
        return hash;
    }

}
